//Accepted
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
using namespace std;

int dp[1000001];
bool no[1000001];
int f(int x){
	if(no[x])return 1;
	if(dp[x]!=-1)return dp[x];
	
	int res = 2000000000;
	int n= (int)sqrt(x);
	
	for(int i=2;i<=n;++i)if(x%i==0)res = min(res, f(i)+f(x/i));
	
	return dp[x]=res;
}

int main(){
	//freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
	memset(dp, -1, sizeof(dp));
	memset(no, 1, sizeof(no));
	int i, j, k, x, t;
	for(i=3, j=4;j<1000001;++i){
		if(no[j])for(k=j;k<1000001;k+=j)no[k]=0;
		j=i*i;
	}
	
	scanf("%d", &t);
	while(t--){
		scanf("%d", &x);
		printf("%d\n", f(x));
	}
}
